package middle;

public class Solution_583 {

    public int minDistance(String word1, String word2) {
        char[] chars_1 = word1.toCharArray();
        char[] chars_2 = word2.toCharArray();

        int[][] arrays = new int[chars_1.length][chars_2.length];
        for (int i = 0; i < chars_1.length; i++) {
            for (int j = 0; j < chars_2.length; j++) {
                if (chars_1[i] == chars_2[j]) {
                    if (i == 0 || j == 0) {
                        arrays[i][j] = Math.max(i, j);
                    } else {
                        arrays[i][j] = arrays[i - 1][j - 1];
                    }
                } else {
                    if (i == 0 && j == 0) {
                        arrays[i][j] = 2;
                    } else if (i == 0) {
                        arrays[i][j] = Math.min(j + 1, arrays[i][j-1]) + 1;
                    } else if (j == 0) {
                        arrays[i][j] = Math.min(i + 1, arrays[i - 1][j]) + 1;
                    } else {
                        arrays[i][j] = Math.min(arrays[i-1][j], arrays[i][j - 1]) + 1;
                    }
                }
            }
        }
        return arrays[chars_1.length - 1][chars_2.length - 1];
//        return dps(chars_1, 0, chars_2, 0);
    }

    // 递归超时
    private int dps(char[] chars_1, int index_1, char[] chars_2, int index_2) {
        if (index_1 == chars_1.length) {
            return chars_2.length - index_2;
        } else if (index_2 == chars_2.length) {
            return chars_1.length - index_1;
        } else {
            if (chars_1[index_1] == chars_2[index_2]) {
                return dps(chars_1, index_1 + 1, chars_2, index_2 + 1);
            } else {
                return Math.min(dps(chars_1, index_1 + 1, chars_2, index_2), dps(chars_1, index_1, chars_2, index_2 + 1)) + 1;
            }
        }
    }

    public static void main(String[] args) {
        Solution_583 model = new Solution_583();
        System.out.println(model.minDistance("dinitrophenylhydrazine", "acetylphenylhydrazine"));
        System.out.println(model.minDistance("sea", "eat"));
        System.out.println(model.minDistance("leetcode", "etco"));
    }
}
